home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 25 / AACD 25.iso / AACD / Magazine / Online / QMail / source / cdbmake_add.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-04-15  |  2.3 KB  |  118 lines
  1. #include "cdbmake.h"
  2.  
  3. void cdbmake_init(cdbm)
  4. struct cdbmake *cdbm;
  5. {
  6.   cdbm->head = 0;
  7.   cdbm->split = 0;
  8.   cdbm->hash = 0;
  9.   cdbm->numentries = 0;
  10. }
  11.  
  12. int cdbmake_add(cdbm,h,p,alloc)
  13. struct cdbmake *cdbm;
  14. uint32 h;
  15. uint32 p;
  16. char *(*alloc)();
  17. {
  18.   struct cdbmake_hplist *head;
  19.  
  20.   head = cdbm->head;
  21.   if (!head || (head->num >= CDBMAKE_HPLIST)) {
  22.     head = (struct cdbmake_hplist *) alloc(sizeof(struct cdbmake_hplist));
  23.     if (!head) return 0;
  24.     head->num = 0;
  25.     head->next = cdbm->head;
  26.     cdbm->head = head;
  27.   }
  28.   head->hp[head->num].h = h;
  29.   head->hp[head->num].p = p;
  30.   ++head->num;
  31.   ++cdbm->numentries;
  32.   return 1;
  33. }
  34.  
  35. int cdbmake_split(cdbm,alloc)
  36. struct cdbmake *cdbm;
  37. char *(*alloc)();
  38. {
  39.   int i;
  40.   uint32 u;
  41.   uint32 memsize;
  42.   struct cdbmake_hplist *x;
  43.  
  44.   for (i = 0;i < 256;++i)
  45.     cdbm->count[i] = 0;
  46.  
  47.   for (x = cdbm->head;x;x = x->next) {
  48.     i = x->num;
  49.     while (i--)
  50.       ++cdbm->count[255 & x->hp[i].h];
  51.   }
  52.  
  53.   memsize = 1;
  54.   for (i = 0;i < 256;++i) {
  55.     u = cdbm->count[i] * 2;
  56.     if (u > memsize)
  57.       memsize = u;
  58.   }
  59.  
  60.   memsize += cdbm->numentries; /* no overflow possible up to now */
  61.   u = (uint32) 0 - (uint32) 1;
  62.   u /= sizeof(struct cdbmake_hp);
  63.   if (memsize > u) return 0;
  64.  
  65.   cdbm->split = (struct cdbmake_hp *) alloc(memsize * sizeof(struct cdbmake_hp));
  66.   if (!cdbm->split) return 0;
  67.  
  68.   cdbm->hash = cdbm->split + cdbm->numentries;
  69.  
  70.   u = 0;
  71.   for (i = 0;i < 256;++i) {
  72.     u += cdbm->count[i]; /* bounded by numentries, so no overflow */
  73.     cdbm->start[i] = u;
  74.   }
  75.  
  76.   for (x = cdbm->head;x;x = x->next) {
  77.     i = x->num;
  78.     while (i--)
  79.       cdbm->split[--cdbm->start[255 & x->hp[i].h]] = x->hp[i];
  80.   }
  81.  
  82.   return 1;
  83. }
  84.  
  85. uint32 cdbmake_throw(cdbm,pos,b)
  86. struct cdbmake *cdbm;
  87. uint32 pos;
  88. int b;
  89. {
  90.   uint32 len;
  91.   uint32 j;
  92.   uint32 count;
  93.   struct cdbmake_hp *hp;
  94.   uint32 where;
  95.  
  96.   count = cdbm->count[b];
  97.  
  98.   len = count + count; /* no overflow possible */
  99.   cdbmake_pack(cdbm->final + 8 * b,pos);
  100.   cdbmake_pack(cdbm->final + 8 * b + 4,len);
  101.  
  102.   if (len) {
  103.     for (j = 0;j < len;++j)
  104.       cdbm->hash[j].h = cdbm->hash[j].p = 0;
  105.  
  106.     hp = cdbm->split + cdbm->start[b];
  107.     for (j = 0;j < count;++j) {
  108.       where = (hp->h >> 8) % len;
  109.       while (cdbm->hash[where].p)
  110.     if (++where == len)
  111.       where = 0;
  112.       cdbm->hash[where] = *hp++;
  113.     }
  114.   }
  115.  
  116.   return len;
  117. }
  118.